package com.example.leetcode.prcatice;

import java.util.*;

public class NewTest752 {
   // 广度优先
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));
        String start = "0000";
        if (set.contains(start)) return -1;
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        Set<String> visit = new HashSet<>();
        visit.add(start);
        int sum = 0;
        while (!queue.isEmpty()){
            int size = queue.size();  // 求出每一层有多少个
            while (size -- >0){
                String poll = queue.poll();
                for (int i =0;i<4;i++){
                    char c = poll.charAt(i);
                   String first = poll.substring(0,i)+(c=='9'? 0:c-'0'+1)+poll.substring(i+1);
                   String second = poll.substring(0,i)+(c == '0'? 9:c-'0'-1)+poll.substring(i+1);
                   if (poll.equals(target)){
                       return sum;
                   }
                   if (!set.contains(first) && !visit.contains(first)){
                       queue.add(first);
                       visit.add(first);
                   }
                   if (!set.contains(second) && !visit.contains(second)){
                       queue.add(second);
                       visit.add(second);
                   }
                }
            }
            sum++;
        }
        return -1;
    }
}
